|
In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it. The special number field sieve is efficient for integers of the form ''r''''e'' ± ''s'', where ''r'' and ''s'' are small (for instance Mersenne numbers). Heuristically, its complexity for factoring an integer is of the form: : in O and L-notations. The SNFS has been used extensively by NFSNet (a volunteer distributed computing effort), (NFS@Home ) and others to factorise numbers of the Cunningham project; for some time the records for integer factorisation have been numbers factored by SNFS. ==Overview of method== The SNFS is based on an idea similar to the much simpler rational sieve; in particular, readers may find it helpful to read about the rational sieve first, before tackling the SNFS. The SNFS works as follows. Let ''n'' be the integer we want to factor. As in the rational sieve, the SNFS can be broken into two steps: *First, find a large number of multiplicative relations among a ''factor base'' of elements of Z/''n''Z, such that the number of multiplicative relations is larger than the number of elements in the factor base. *Second, multiply together subsets of these relations in such a way that all the exponents are even, resulting in congruences of the form ''a''2≡''b''2 (mod ''n''). These in turn immediately lead to factorizations of ''n'': ''n''=gcd(''a''+''b'',''n'')×gcd(''a''-''b'',''n''). If done right, it is almost certain that at least one such factorization will be nontrivial. The second step is identical to the case of the rational sieve, and is a straightforward linear algebra problem. The first step, however, is done in a different, more efficient way than the rational sieve, by utilizing number fields. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Special number field sieve」の詳細全文を読む スポンサード リンク
|